""" 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ """
'''
当前层有x个1和y个2，2在下一层直接加1，1在下一层可以加1，也可以合并下一层成2，
所以下一层就有x个2和y+x个1，
'''


class Solution:
    def climbStairs(self, n: int) -> int:
        bp = [
            [1, 0],
        ]  # 开局一个台阶所以1个一步，0个两布
        for i in range(n):
            bp.append([bp[i][0] + bp[i][1], bp[i][0]])
        return bp[-2][0] + bp[-2][1]
